
	
SimulatedAnnealing::SimulatedAnnealing( const char* input_file ) : Algorithm( input_file ){
}

SimulatedAnnealing::~SimulatedAnnealing(){
}

int* SimulatedAnnealing::initHeuristic(){
	int index[L];
	for( int i = 0; i < L; ++i )
		index[i] = i;
	
	for( int i = 0; i < L; ++i )
		swap( &index[i], &index[rand()%L] );
	
	int *init_solution = new int[k];
	for( int i = 0; i < k; ++i )
		init_solution[i] = index[i];
		
	return init_solution;
}

void SimulatedAnnealing::solve(){
	
	float t = 10000;
	float t0 = t;
	float alfa = 0.99;
	
	int* S = initHeuristic();
	
	int quality_s = getSolutionQuality(S);
	
	quality_best = quality_s;
	
	time_t start = time(NULL);
	
	do{
		float a = t/t0;
		float b = alfa;
		int iterations = log10(a)/log10(b)+1;
		
		//int iterations = (int)t0/t;

		while(iterations){
			
			int* neighbor = VNS(S);
			int quality_neighbor = getSolutionQuality(neighbor);
			
			float param = ((float)(quality_neighbor-quality_s))/t;
			float random_number = (float)rand()/(float)RAND_MAX;
			
			if(quality_neighbor > quality_best || random_number < exp(param)){
				copySolution(S, neighbor);
				quality_s = quality_neighbor;
				
				if(quality_neighbor > quality_best)
					quality_best = quality_neighbor;
				
				/*
				cout << "aqui1" << endl;
				cout << best << endl;
				print(new_solution,k);
				intersection_set.print();
				//*/
			}
			delete [] neighbor;
				
			--iterations;
		}
		t = alfa*t;
		if(t-EPS <= 0)
			t = 10000;
	}while((time(NULL) - start < 60));
	
	
	
}

int* SimulatedAnnealing::VNS(int* S){
	int* ret = new int[k];
	copySolution(ret,S);
	int quality_ret = getSolutionQuality(ret);
	
	for(int i = 1; i <= k; ++i ){
		int* new_solution = changeN(S, i);
		
		int quality_new_solution = getSolutionQuality(new_solution);
		
		if(quality_new_solution > quality_ret){
			copySolution(ret,new_solution);
			quality_ret = quality_new_solution;
			i = 0;
		}
		delete [] new_solution;
	}
	return ret;
}

int* SimulatedAnnealing::changeN(int* S, int n){
	
	int is_in_solution[L];
	memset(is_in_solution,0,L*sizeof(int));
	
	for( int i = 0; i < k; ++i )
		is_in_solution[S[i]] = 1;
	
	int* new_solution = new int[k];
	
	int changes[k];
	for(int i = 0; i < k; ++i){
		changes[i] = i;
		new_solution[i] = S[i];
	}
	
	for(int i = 0; i < k; ++i)
		swap(&changes[i], &changes[rand()%k]);
	
	int set_to_be_inserted;
	for(int i = 0; i < n; ++i){
		int set_to_be_inserted;
		
		int sets_to_be_inserted[L];
		for(int l = 0; l < L; ++l)
			sets_to_be_inserted[l] = l;
		
		for(int l = 0; l < L; ++l)
			swap(&sets_to_be_inserted[l], &sets_to_be_inserted[rand()%L]);
		
		for(int l = 0; l < L; ++l){
			if(!is_in_solution[sets_to_be_inserted[l]]){
				set_to_be_inserted = sets_to_be_inserted[l];
				break;
			}
		}

		is_in_solution[new_solution[changes[i]]] = 0;
		new_solution[changes[i]] = set_to_be_inserted;
		is_in_solution[new_solution[changes[i]]] = 1;
	}
	
	return new_solution;
}

int SimulatedAnnealing::getSolutionQuality(int* s){
	Set temp;
	temp.union_(&sets[s[0]]);
	
	for( int i = 1; i < k; ++i )
		temp.intersection(&sets[s[i]]);

	return temp.cardinality();
}

void SimulatedAnnealing::copySolution(int* s1, int* s2){
	for( int i = 0; i < k; ++i )
		s1[i] = s2[i];
}

int SimulatedAnnealing::getQualityOfBest(){
	return quality_best;
}
